There are a number of problems with communication systems. A major challenge in signal recovery in mobile communications is to recover symbols from a signal transmitted over multiple channels in the presence of channel fading and distortion. In many communication systems, receivers observe the sum of multiple transmitted signals due to multi-paths, plus any noise. In addition, as a mobile transmitter proceeds along its route, the communication environment is constantly changing. That results in received signals that are displaced with respect to time, space, and frequency. Therefore, many wireless communication systems operate under highly dynamic conditions due to the mobility of the transceivers, varying environmental conditions, and the random nature of channel access. Equalization of multipath channels and detecting signals in receivers poses many difficulties.
In wireless communication systems, mobile transmitters send symbols at a high data rate. Multiple copies of the signal, with delays, can interfere with the main signal. This is referred to as “delay spread,” and causes inter-symbol interference (ISI). As a result, equalizers may be required. Equalization with training sequences is widely used in many communication systems. However, in applications such as multipoint communication networks, it is desired to have synchronization and equalization without using a training sequence.
In fast fading channels, training sequences can be a large overhead and may significantly reduce channel throughput. Therefore, blind equalization techniques with joint channel estimation and signal detection is often required. Various methods for blind equalization are known in the prior art, including methods using stochastic gradient algorithm and higher order signal statistics. However, a primary drawback of those methods is the slow convergence of channel estimation, often requiring 10000–50000 symbols before an acceptable channel estimate is obtained.
Maximum Likelihood Sequence Estimation
A widely used blind equalization method is based on maximum likelihood sequence estimation (MLSE). For a simplified discrete-time finite channel model h(k), k=0, 1, . . . , L, given the transmitted symbols x(n), n=1, 2, . . . , N, the received sequence y(n), n=1, 2, . . . , N can be expressed as:
                                          y            ⁡                          (              n              )                                =                                                    ∑                                  k                  =                  0                                L                            ⁢                                                h                  ⁡                                      (                    k                    )                                                  ⁢                                  x                  ⁡                                      (                                          n                      -                      k                                        )                                                                        +                          v              ⁡                              (                n                )                                                    ,                            (        1        )            where the variable v(n) is an independent and identically distributed (i.i.d.) additive Gaussian noise with zero mean and variance σ2. For a block of N received symbols, the probability density function of the received sequence y(n), conditioned on knowing the channel model h(n) and transmitted symbols x(n) is:
                              p          ⁡                      (                                          y                |                h                            ,              x                        )                          =                              1                                          (                                  2                  ⁢                                                                          ⁢                  π                  ⁢                                                                          ⁢                                      σ                    2                                                  )                            N                                ⁢                                    exp              ⁡                              (                                                                            -                                              1                                                  2                          ⁢                                                                                                          ⁢                                                      σ                            2                                                                                                                ⁢                                          ∑                                              n                        =                        1                                            N                                                        |                                                            y                      n                                        -                                                                  ∑                                                  k                          =                          0                                                L                                            ⁢                                                                        h                          k                                                ⁢                                                  x                                                      n                            -                            k                                                                                                                                ⁢                                      |                    2                                                  )                                      .                                              (        2        )            
The blind equalization essentially estimates the channel impulse response h and the transmitted data x only from a set of observations y. Equivalently, the solution minimizes the following cost function over h and x,
                                          J            ⁡                          (                              h                ,                x                            )                                =                                                    ∑                                  n                  =                  1                                N                            ⁢                              |                                                      y                    n                                    -                                                            ∑                                              k                        =                        0                                            L                                        ⁢                                                                  h                        k                                            ⁢                                              x                                                  n                          -                          k                                                                                                                    ⁢                                  |                  2                                                      =                                                                            y                  -                                      A                    ⁢                                                                                  ⁢                    h                                                                              2                                      ,                            (        3        )            where A is
                    A        =                              [                                                                                x                    1                                                                    0                                                  …                                                  0                                                                                                  x                    2                                                                                        x                    1                                                                    …                                                  0                                                                              …                                                  …                                                  …                                                  …                                                                                                  x                    N                                                                                        x                                          N                      -                      1                                                                                        …                                                                      x                                          N                      -                      L                                                                                            ]                    .                                    (        4        )            
When the input signal is known by minimizing equation (3), the maximum likelihood channel estimation can be obtained by:hML(x)=(AtA)−1Aty.  (5)
On the other hand, when the channel impulse response is known, the maximum likelihood sequence of the source symbols can be obtained using the Viterbi algorithm. When neither h and x are known, a direct approach is to determine the maximum likelihood estimate of the channel impulse response h for each possible data sequence x. Then, the data sequence that minimizes the cost function J(h,x) for each corresponding channel estimate is selected. Obviously, this exhaustive search approach has a large computational complexity that makes it impossible to use in practice when the number of symbols received increases.
The typical maximum likelihood based joint channel estimation and signal detection method generally includes initial channel estimation, followed by alternative signal detection and channel update steps.
Typical prior art methods operate alternately between parameter estimation, assuming that the symbols are known, and a Viterbi sequence detection, assuming that the channel parameters are known. One potential drawback of those methods is that they are very sensitive to the initial guess of the channel parameters, e.g., see Kaleh et al., “Joint parameter estimation and symbol detection for linear or nonlinear unknown channels,” IEEE Trans. on Communications, Vol. 42, No. 7, PP. 2406–2413, July, 1994, and Feder et al., “Algorithms for joint channel estimation and data recovery—application to equalization in underwater communications,” IEEE Journal of Oceanic Engineering, Vol. 16, No. 1, PP. 42–55, January, 1991.
Quantized channel estimation methods can also be used. Those methods are generally less sensitive to the initial channel estimate, e.g., see Zervas et al., “A quantized channel approach to blind equalization,” Proc. IEEE ICC'92, Vol. 3, pp. 1539–1543, 1992. While that method has its advantage in a parallel structure and robustness to the initial estimate of the channel parameters, its complexity increases exponentially with the order of the channel due to operating multiple Viterbi algorithms simultaneously.
Another prior art method for joint blind channel estimation uses parallel adaptive general Viterbi algorithm to determine multiple estimated channels for symbol detection, see Seshadri et al., “List Viterbi decoding algorithms with applications,” IEEE Trans. on Communications, Vol. 42, No. 2/3/4, pp. 313–323, February, 1994, and Seshadri “Joint data and channel estimation using blind trellis search techniques,” IEEE Trans. on Communications, Vol. 42, No. 2/3/4, pp. 1000–1011, 1994, and U.S. Pat. No. 5,263,033 “Joint data and channel estimation using fast blind trellis search,” issued to Seshardi on Nov. 16, 1993. Because multiple channel estimates are maintained concurrently during each time instant, this method requires more computational resources than the conventional Viterbi algorithm. More important, that method does not guarantee the best convergence performance even though it can quickly achieve a rough channel estimate. That is because when channel estimation converges, noise may cause the method to select randomly from different channel estimates at each step. The channel estimates are updated immediately after path metrics are determined. Therefore, a single high noise value can diverge the direction of channel update and result in a non-optimal channel estimate. In addition, the number of trellis mappings derived by Seshadri isNtre=2L(2L+1−2)(2L+1−4) . . . (4)(2)(1)=22L(2L)!/2.
That value is much higher than the minimal number of trellis mappings desired for effective channel estimation.
To summarize, the less complicated methods of the prior art channel estimation and symbol detection are sensitive to the initial channel estimate, while robust initial estimates are very computationally complex.